Dr. Man Young Rhee, in his book "Cryptography and Secure Communications" (McGraw-Hill, 1994) states on page 12: "A cryptosystem which can resist any cryptanalytic attack, no matter how much computation is allowed is said to be unconditionally secure. The one time pad is the only unconditionally secure cipher in use. One of the most remarkable ciphers is the one-time pad in which the ciphertext is the bit-by-bit modulo-2 sum of the plaintext and a nonrepeating keystream of the same length. However, the one-time pad is impractical for most applications because of the large size of the nonrepeating key."
U.S. Pat. No. 5,113,444 issued May 12, 1992 entitled "RANDOM CHOICE CIPHER SYSTEM AND METHOD" states "First random number strings are a relatively scarce commodity. Second, the receiver must have at hand exactly the same random number sequence the sender used or must be able to reproduce it. The first of these alternatives requires the sharing of an enormous amount of key material. The sharing of an enormous amount of key material is impractical. The second alternative is impossible." The first and second conclusions to these statements are inaccurate. Statistical analysis of the sampling of digital sources (specifically 16 bit sound files) shows that random or arbitrary numbers or bytes are readily available in the digital/computer environment. This ready availability of random numbers is contrary to the teachings and opinions of those skilled in the art as well as those expert in the art of cryptography.
Another prevailing view of those skilled in the art is that most pseudo-random numbers have an inherent weakness because they are generated by a formula and that it may be possible to reconstruct the formula and then predict the numbers in the series.
U.S. Pat. No. 4,751,733 entitled "SUBSTITUTION PERMUTATION ENCIPHERING DEVICE" describes in the abstract: "A substitution-permutation enciphering device. This device, adapted for transforming a binary word into another binary word, by succession of substitutions and permutations, under the control of a key . . . " teaches away from the scheme described herein. The use of a substitution memory as described by U.S. Pat. No. 4,751,733 has a limitation in that this patent discloses and teaches changes only to the bits of a byte.
U.S. Pat. No. 5,001,753 entitled "CRYPTOGRAPHIC SYSTEM AND PROCESS AND ITS APPLICATION" describes the use of a rotational operator in an accumulator. The rotation operation is used to cause an accumulator bit to be temporarily stored in the carry bit, rather than in a memory location, and the carry bit (regardless of its value) is ultimately rotated back into its original position. The rotate operation is explained in detail by column 3 line 61 through column 4 line 6. Also described is the processing within a microprocessor using an eight bit (1 byte) accumulator. The '753 patent is limited to the rotate operation in conjunction with an accumulator.
U.S. Pat. No. 5,113,444, entitled "RANDOM CODING CIPHER SYSTEM AND METHODS," and U.S. Pat. No. 5,307,412, teach the use of a thesaurus and/or synonyms together with arithmetic/logic operations to combine data and masks to accomplish encoding/decoding. These patents are thus limited by the use of the thesaurus and synonyms.
U.S. Pat. No. 5,412,729 entitled "DEVICE AND METHOD FOR DATA ENCRYPTION" introduces the concept of using matrix operations to multiplex the bytes in the cleartext so that a byte in the ciphertext may contain elements of more than one cleartext bytes. The patent teaches about the multiple use of a data element to create a ciphertext element. This is different from the combination of: creating a single working element by concatenating several bytes together (with permutation of sequence during the concatenation), binary rotating the resultant single element, and the breaking up the single element back into multiple bytes to be placed in an output buffer (also with permutation of sequence). Under certain conditions, a matrix presentation may be used to represent the effect of the rotation operation. However, careful examination will show that the matrix representation of the rotation operation does not follow the rules associated with a linear system and thus is quite different from this patent. This patent method is limited by teaching the multiplexes several different data elements together wherein each element may be used more than once, while the scheme herein only modifies a single data element at any one time.
U.S. Pat. No. 5,077,793 entitled "RESIDUE NUMBER ENCRYPTION AND DECRYPTION SYSTEM" teaches (column 3 lines 40 to column 4 lines 8): "if the moduli are chosen to be mutually prime, then all integers with the range of zero to the product of the moduli minus one can be uniquely represented. The importance of the residue number system to numerical process is that the operations of addition, subtraction, and multiplication can be performed without the use of carry operations between the moduli. In other words, each digit in the n-tuple can be operated on independently and in parallel." And shows that for the sum Z of the digits X and Y, the ith digit may be given by: z.sub.i =(x.sub.i +y.sub.i) mod m.sub.i and that "a sixteen bit binary number can be represented in the residue number system using five moduli 5,7,11,13,17." The moduli (m.sub.i) are chosen to be relatively prime to each other. In Columns 5 and 6 the description goes on to define Z=(X+Y) mod M (where M is the product of all of the moduli, i.e., M=m.sub.1 .times.m.sub.2 . . . m.sub.n,) as a generalization of the Vigenere cipher. If Z=(X-Y) mod M is used to encrypt X using Y then X may be recovered from Z by X=(Y-Z) mod M, which is a generalization of the Beaufort cipher.
Pages 305 and 306 in "Applied Cryptography, Second Edition" by Bruce Schneier, John Wiley & Sons, Inc. 1996--describe the Madryga encryption method. "The Madryga consists of two nested cycles. The outer cycles repeats eight time (although this could be increased if security warrants) and consists of an application of the inner cycle to the plaintext. The inner cycle transforms plaintext to ciphertext and repeats once for each 8-bit block (byte) of the plaintext. Thus the algorithm passes through the entire plaintext eight successive times. An iteration of the inner cycle operates on a 3-byte window of data, called the working frame [figure reference omitted]. This window advances 1 byte for each iteration. (The data are considered circular when dealing with the last 2 bytes.) The first 2 bytes of the working frame are together rotated a variable number of positions, while the last byte is XORed with some key bits. As the working frame advances, all bytes are successively rotated and XORed with key material. Successive rotations overlap the results of a previous XOR and rotation, and the data from the XOR is used to influence the rotation. This makes the entire process reversible. Because every byte of data influences the 2 bytes to its left and the 1 byte to its right, after eight passes every byte of the ciphertext is dependent upon 16 bytes to the left and 8 bytes to the right. When encrypting, each iteration of the inner cycle starts the working frame at the next-to-last byte of the plaintext and advances circularly through to the third-to-last byte of the plaintext. First, the entire key is XORed with a random constant and then rotated to the left 3 bits. The low-order 3 bits of the low-order byte of the working frame are saved; they will control the rotation of the other 2 bytes. Then, the low-order byte of the working frame is XORed with the low-order byte of the key. Next, the concatenation of the 2 high-order bytes are rotated to the left the variable number of bits (0 to 7). Finally, the working frame is shifted to the right 1 byte and the whole process repeats." On page 306, "Both the key and the 2 ciphertext bytes are shifted to the right. And the XOR is done before the rotations." The Madryga method may be improved upon by a better randomizing of the order of the bytes prior to concatenation and by not storing the rotate distance information (even though it is encrypted) in the data itself. A weakness of this method is that the order of the bytes prior to concatenation is unmodified and therefore more easily broken.
The terms engine, encoder, decoder are used interchangeably herein.
Herein a relative address pointer (rap or RAP) is defined as relative address index, pointing to an entry within a table of bytes, an array of bytes or an I/O buffer. When relative addresses are supplied by a counter, that counter is constructed so that it counts modulo the size of the I/O Buffer, Mask Array, or table with which it is associated. When the size of an array or I/O buffer is a power of 2 in length, then an ordinary binary counter may usually be used to supply the relative address pointers.
Address scrambling is defied herein as the modification of a relative address pointer (RAP) so that its value is changed through the uses of any combination of: additive (or subtractive) values, XORing (exclusive-or) of mask values or by table lookup values, creating a scrambled relative address pointer (srap or SRAP).
Address Translation Table operations are defined herein as ATT Operations. This will mean the converting of a relative address pointer (RAP) into a scrambled relative address pointer (SRAP).
ATT Entries, or ATT Block Entries, or ATT Blocks, are defined herein as tables of relative address pointers or modified relative index values 2.sup.N in size, having values of 0 to .sub.2.sup.N -1. Other sized ATT Block Entries may be used for non-power-of 2 XORn and ATT Block Entry Modulo operations. For example, an ATT Block of 1014 entries will use an XORn (based 13) and a Modulo operation of 1014. Each ATT Block contains only 1 unique value in its range. There are no duplicate entry values and thus an ATT Block is completely different from a thesaurus as defined in either U.S. Pat. No. 5,113,444 or U.S. Pat. No. 5,307,412 because no synonyms or duplicate entries are present. The size of the I/O buffers and Masking Arrays should be an integer multiple of the ATT Block Entries to be used with them. Thus if a ATT Block Entry for I/O is 1000, then the I/O Buffers should be integer multiples of 1000 bytes in size. If the masking arrays are 64K in size, then a ATT Block Entry for them should be a power of 2 in size less than or equal to 64K. A buffer size of 1014 is interesting if 3 byte (24 bit wide) arithemetic/logic operations are chosen.
ATT Column is defined herein as a collection of one or more ATT Blocks used one at a time so that even though the collection of multiple ATT Blocks all contain the same entries, though probably in a different order, they are not a table of Synonyms as defined by either U.S. Pat. No. 5,113,444 or U.S. Pat. No. 5,307,412. Also these ATT Blocks are used to modify the value of a relative address pointers and not the data to be encrypted or decrypted as is done by these patents.
Herein ATTN is the number of ATT Blocks in an ATT Column. Herein ATTSIZE is the ATT Block size within an ATT Column and ATT BASE is the number base for the XORn masking operations to be used with the ATT Block size. Herein ATTB is the number of the ATT Block Entry being used (counting from 0 upwards) within an ATT Column. Herein an Address Translation Table consist of one or more ATT columns.
Multiple byte fetches (MF's) are/is defined as the accessing from a mask array, table or buffer, of two or more bytes to create a single element comprising the logical concatenation of the bytes retrieved. Herein MF will refer to multibyte fetch operations.
Decatenation or decatenate are defined herein as the breaking apart of a single multibyte width entity, previously created by the concatenation of individual bytes, back into individual bytes.
Multiple byte put (MP) is defined herein as the breaking up, or decatenation, of a logical concatenation of bytes into 2 or more individual bytes and their placement into a table or buffer.
A byte is defined herein as being of any width greater than or equal to 2 bits.
Herein array is defined as an actual grouping of two or more elements and as a logical grouping of two or more elements, wherein an element is a bit, digit, byte or word of any length.
A barrel shifter is defined herein as being a shift register arranged such that any bits shifted off either end of the register are also shifted back in the other end of the shift register at the same time. No information is added, lost or changed in the process. A barrel shifter may also be constructed using a simple latch register and multiple selects for the inputs to the latch creating a barrel shifter which only requires one clock period to perform any size rotate. Rotation can also be performed in a register within most typical CPUs. Usually, there is an instruction native to the CPU which will perform this operation.
Herein the words, rotation, rotational operation, or rotation operation will refer to barrel shifting.
Herein an encoder pass, or PASS, is defined to mean the encoding of a block of cleartext into an intermediate-text or ciphertext block, or the decoding of a block of ciphertext into an intermediate-text or cleartext block.
BCN is defined herein as the binary to base n conversion of a number and the representation of the base n number as a digit shown in binary. A common example (base 10) is BCD (binary coded decimal) where the values 0 through 9 are represented by 4 binary bits.
It is an object of the present invention to provide a source of random, pseudo-random and arbitrary numbers to be used in the encryption/decryption processes and devices.
It is an object of the present invention to provide a concatenation operation which is used to create a single data element from smaller elements, and after modification, the single element is split up into smaller elements again - with each smaller element being used only one time.
It is yet another object of the present invention to exclude the use of thesauruses and of synonyms.
It is still another object of the present invention to provide encryption/decryption apparatus and methods wherein information data, which is to be securely transmitted between users, are permuted and shifted. The resulting information may then be combined with masking data from random, pseudo-random, or arbitrary sources to provide another level of encoding/decoding for further security.